package leetcode_1000;

import java.util.TreeSet;

public class KClosestPointsToOrigin_973 {
	class Help{
		int dis;
		int index;
		public Help(int dis,int index) {
			this.dis = dis;
			this.index = index;
		}
	}
	public static void main(String[] args) {
		KClosestPointsToOrigin_973 test=new KClosestPointsToOrigin_973();
		test.kClosest(new int[][]{{3,3},{5,-1},{-2,4}}, 2);
	}
	
	public int[][] kClosest(int[][] points, int K) {
        TreeSet<Help> set=new TreeSet<Help>((o1,o2)->o1.dis-o2.dis);
        for(int i=0;i<points.length;++i) {
        	int dis = points[i][0]*points[i][0]+points[i][1]*points[i][1];
        	set.add(new Help(dis, i));
        	if(set.size()>K)
        		set.pollLast();
        }
        int [][]res =new  int[K][2];
        for(int i=0;i<K;++i) {
        	Help now=set.pollFirst();
        	res[i][0]=points[now.index][0];
        	res[i][1]=points[now.index][1];
        }
        return res;
    }
}
